home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / simula / books / books.lha / kirkerud / binsearch.sim < prev    next >
Text File  |  1993-08-16  |  1KB  |  31 lines
  1. procedure Binary_search_in_table(table, low_bound, high_bound,
  2.                              search_value, value_found, index_of_value);
  3.     name value_found, index_of_value;
  4.     integer array table;
  5.     integer low_bound, high_bound, search_value, index_of_value;
  6.     Boolean value_found;
  7.   if low_bound > high_bound or
  8.      search_value < table(low_bound) or
  9.      search_value > table(high_bound)
  10.   then value_found := false else
  11.   begin integer middle;
  12.     while low_bound + 1 < high_bound do
  13.       begin
  14.           ! At this place it is always the case that
  15.           ! table(low_bound) <= search_value <= table(high_bound);
  16.         middle := (low_bound + high_bound)//2;
  17.         if table(middle) <= search_value
  18.           then low_bound  := middle 
  19.           else high_bound := middle;
  20.       end;
  21.       ! At this place it is always the case that
  22.       ! 1: table(low_bound) <= search_value <= table(high_bound);
  23.       ! 2: Either: low_bound + 1 = high_bound;
  24.       !        or: low_bound     = high_bound;
  25.     if search_value = table(high_bound) then
  26.       begin value_found := true; index_of_value := high_bound end else
  27.     if search_value = table(low_bound) then
  28.       begin value_found := true; index_of_value := low_bound end
  29.     else value_found := false;
  30.   end of Binary_search_in_table;
  31.